package com.gjx.leetcode;
//106. 从中序与后序遍历序列构造二叉树
//根据一棵树的中序遍历与后序遍历构造二叉树。
//
//注意:
//你可以假设树中没有重复的元素。
//
//例如，给出
//
//中序遍历 inorder = [9,3,15,20,7]
//后序遍历 postorder = [9,15,7,20,3]
//返回如下的二叉树：
//
//    3
//   / \
//  9  20
//    /  \
//   15   7


public class Solution106 {
	public TreeNode buildTree(int[] inorder, int[] postorder) {
        return build(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }
	
	
	private TreeNode build(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd) {
		
		if (inorderStart > inorderEnd) {
			return null;
		} else if (inorderStart == inorderEnd) {
			return new TreeNode(inorder[inorderStart]);
		}
		
		
		TreeNode root = new TreeNode(postorder[postorderEnd]);
		
		int len = 0;
		
		for (int i=inorderStart; i<=inorderEnd; i++) {
			if (inorder[i] == postorder[postorderEnd]) {
				len = i - inorderStart;
			}
		}
		
		TreeNode left = build(inorder, inorderStart, inorderStart+len-1, postorder, postorderStart, postorderStart+len-1);
		TreeNode right = build(inorder, inorderStart+len+1, inorderEnd, postorder, postorderStart+len, postorderEnd-1);
		
		root.left = left;
		root.right = right;
		
		return root;
		
	}
	
	
}
